package ch09_10;

import java.util.*;

/**
 * Good Question.
 * Consult wikipedia for Longest_Increasing_Subsequence.
 * @author ryan
 *
 */
class Box implements Comparable<Box> {
    int w;
    int h;
    int d;
    public Box(int w, int h, int d) {
	this.w = w;
	this.h = h;
	this.d = d;
    }

    public boolean largerThan(Box box) {
	return w > box.w && h > box.h && d > box.d;
    }

    public int compareTo(Box box) {
	if (h > box.h) {
	    return 1;
	} else if (h < box.h) {
	    return -1;
	} else {
	    return 0;
	}
    }

    public String toString() {
	return "(" + w + ", " + h + ", " + d + ")";
    }

}
public class Solution {

	public static void highest(Box[] boxes) {
	Arrays.sort(boxes);
	int N = boxes.length;
	int[] dp = new int[N];
	int[] trackBack = new int[N];
	int highest = 0;
	int index = 0;
	dp[0] = boxes[0].h;
	for (int i = 1; i < N; i++) {
	    dp[i] = boxes[i].h;
	    trackBack[i] = i;
	    for (int j = 0; j < i; j++) {
		if (boxes[i].largerThan(boxes[j])) {
		    if (dp[i] < dp[j] + boxes[i].h) {
		    	dp[i] = dp[j] + boxes[i].h;
		    	trackBack[i] = j;
		    }
		}
	    }
	    if (dp[i] > highest) {
		highest = dp[i];
		index = i;
	    }
	}
	System.out.println("highest is " + highest);
	int previous = 0;
	do {
	    System.out.println("box No." + index);
	    previous = index;
	    index = trackBack[index];
	} while (index != previous);
	System.out.println();
    }

    public static void highest_1(Box[] boxes) {
	Arrays.sort(boxes);
	int N = boxes.length;
	int[] dp = new int[N];
	dp[0] = boxes[0].h;
	int highest = 0;
	for (int i = 1; i < N; i++) {
	    dp[i] = boxes[i].h;
	    for (int j = 0; j < i; j++) {
		if (boxes[i].largerThan(boxes[j])) {
		    dp[i] = Math.max(dp[i], dp[j] + boxes[i].h);
		}
	    }
	    if (dp[i] > highest) {
		highest = dp[i];
	    }
	}
	System.out.println("highest_1: " + highest);
    }

    private static final int _10 = 15;

    public static Box randomInit() {
	int base = 1 + (int)(10 * Math.random());
	int w = base + (int)(_10 * Math.random());
	int h = base + (int)(_10 * Math.random());
	int d = base + (int)(_10 * Math.random());
	return new Box(w, h, d);
    }

    public static void main(String... args) {
	int N = 10;
	Box[] boxes = new Box[N];
	for (int i = 0; i < N; i++) {
	    boxes[i] = randomInit();
	}
	Arrays.sort(boxes);
	System.out.println(Arrays.toString(boxes));
	highest_1(boxes);
	highest(boxes);
    }
}